#include <iostream>
#define ERROR -1
#define OK 0

using namespace std;

//定义节点
class Node
{
    public:
        char data;
        Node *pre;   //指向前继的指针
        Node *next;  //指向后继的指针
        //构造函数
        Node(){
            next=NULL;
            pre = NULL;
        }
};

//定义栈处理对象
class Stack
{
    private:
        Node *top;  //栈顶元素指针
        Node *base;  //栈尾元素指针
        Node *initNode;  //初始化的头指针
        int size;  //栈内元素长度
        int initSize;  //初始化的栈长度
    public:
        //初始化
        Stack(int n){
            base =NULL;
            top = NULL;
            size =0;
            initSize = n>0?n:0; 
            base = new Node();
            initNode = top = base;

            Node *tmpNode;
            for(int i=1;i<initSize;i++){
                tmpNode = new Node();
                tmpNode->data = 0;
                tmpNode->next = initNode; //要插入的空节点指向当前第一个节点
                initNode->pre = tmpNode;  //头结点指向新来的元素
                initNode = tmpNode;       //移动头结点指针指向新插入的节点
            }
            return ;
        }

        bool isEmpty(){
            return (base == top && size ==0);
        }

        bool isFull(){
            return initSize > size ? false :true;
        }

        int getSize(){
            return size;
        }

        //插入元素为新的栈顶元素
        int push(char e)
        {
            Node *tmpNode;
            if(isFull()){
                //如果栈满了，则创建新的节点
                tmpNode = new Node();
                tmpNode->data = e;
                tmpNode->next = top->next;
                initNode = top = tmpNode;
                size++;
            }else if(isEmpty()){
                top->data = e;
                size =1;
            }else{
                //否则往上移动栈顶指针,压入新的元素
               top = top->pre;
               top->data = e; 
               size++;
            }

            return OK; 
        }

        //弹出栈顶元素
        char pop()
        {
            char a =0;
            if(!isEmpty()){
                a = top->data;
                top = top->next;
                size--;
                return a;
            }else{
                return a;
            }
        }

        //打印栈的元素
        int output(){
            Node *tmpNode;
            tmpNode = top;
            cout << "\n栈的长度为:"<< size <<" top->base:";
            for(int i=0; i<size;i++){
                cout << tmpNode->data << " ";
                if(tmpNode != base){
                    tmpNode = tmpNode->next;
                }

            }
        }
};
